package com.test.daily.leetcode.y2022.m06.day0613.v02;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/13 上午 11:31
 * @version: 1.0
 */
public class Solution {
    public static int splitCount(int num) {
        if (num <= 0) {
            return 0;
        }
        if (num == 1) {
            return 1;
        }
        return process(1, num);
    }

    public static int process(int pre, int rest) {
        if (rest > pre) {
            return 0;
        }
        if (rest == 0) {
            return 1;
        }
        int ways = 0;
        for (int first = 1; first <= rest; first++) {
            ways += process(first, rest - first);
        }
        return ways;
    }

    public static int dp(int num){
        int[][] dp = new int[num + 1][num +1];
        for(int pre = 0; pre <= num; pre++){
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for(int pre = num-1; pre >= 0; pre--){
            for(int rest = pre; rest <= num; rest++){
                int ways = 0;
                for(int first = 1; first <= rest; first++){
                    ways += dp[first][rest-first];
                }
                dp[pre][rest] = ways;
            }
        }
        return dp[1][num];
    }

    public static int dp2(int num){
        int[][] dp = new int[num+1][num+1];
        for(int pre = 1; pre <= num; pre++){
            dp[pre][0] = 1;
            dp[pre][pre] = 1;
        }
        for(int pre = num-1; pre >=0; pre--){
            for(int rest = pre + 1; rest <= num; rest++){
                dp[pre][rest] = dp[pre+1][rest];
                dp[pre][rest] += dp[pre][rest-pre];
            }
        }
        return dp[1][num];
    }

}
